def MAX_LENGTH_LIST(nums):
    if len(nums) == 0:
        return 0, []

    # 生成dp数组，初始化为1
    dp = [1 for _ in range(len(nums))]
    # 数组用于存储LIS中前一个元素的索引
    prev = [-1 for _ in range(len(nums))]

    # 计算以每个索引结尾的LIS的长度
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                prev[i] = j

    # 找到LIS的最大长度
    max_length = max(dp)
    index = dp.index(max_length)

    # 重建LIS
    lis = []
    while index != -1:
        lis.append(nums[index])
        index = prev[index]

    # 反转LIS以得到正确顺序
    lis.reverse()

    return max_length, lis


nums = [10, 9, 2, 5, 3, 7, 101, 18]
max_length, lis = MAX_LENGTH_LIST(nums)
print("最长递增子序列: {}".format(lis))
print("长度为: {}".format(max_length))
